/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXI30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=XMAS25/FONT#8=MISC25
␈↓ α∧␈↓Finitary Search␈↓ εP␈↓πdraft␈↓␈↓ 
IMarch 4, 1976


␈↓ α∧␈↓α␈↓ ∧yFINITE STATE SEARCH PROBLEMS




␈↓ α∧␈↓α␈↓ ¬
John McCarthy, Stanford University




␈↓ α∧␈↓α␈↓ αT1. Introduction

␈↓ α∧␈↓␈↓ αTWe␈αhave␈αfound␈αa␈αclass␈αof␈αsearch␈αproblems␈αthat␈αmay␈αadmit␈αvery␈αefficient␈αalgorithms␈αand␈αto
␈↓ α∧␈↓which␈αmany␈αsearch␈αproblems␈αthat␈αarise␈α
naturally␈αcan␈αbe␈αreduced.␈α The␈αreduction␈αitself␈α
will␈αoften
␈↓ α∧␈↓be␈α
a␈α
more␈α
difficult␈α
heuristic␈α
problem␈α
than␈α
the␈α
subsequent␈α
solution,␈α
but␈α
nevertheless␈α
this␈α∞way␈α
of
␈↓ α∧␈↓dividing problems may often be the best way of conquering them.

␈↓ α∧␈↓␈↓ αTThe␈αmethods␈α
to␈αbe␈α
described␈αare␈α
applicable␈αto␈αwhat␈α
I␈αwant␈α
to␈αcall␈α
␈↓↓non-mental␈αquasi-static
␈↓ α∧␈↓↓problems␈↓.␈α
 "Quasi-static"␈α∞means␈α
that␈α
each␈α∞action␈α
of␈α
the␈α∞problem␈α
solver␈α
gives␈α∞rise␈α
to␈α
a␈α∞new␈α
state,
␈↓ α∧␈↓and␈α
the␈α
problem␈α
is␈α
to␈α∞find␈α
a␈α
sequence␈α
of␈α
actions␈α
leading␈α∞from␈α
an␈α
initial␈α
state␈α
to␈α
a␈α∞state␈α
having
␈↓ α∧␈↓desired␈α∞properties.␈α∞ "Non-mental"␈α∞means␈α∞that␈α∞the␈α∂problem␈α∞is␈α∞to␈α∞be␈α∞solved␈α∞with␈α∂the␈α∞information
␈↓ α∧␈↓provided;␈α∀strategies␈α∀to␈α∀acquire␈α∀additional␈α∃information␈α∀are␈α∀not␈α∀required.␈α∀ Almost␈α∀all␈α∃of␈α∀the
␈↓ α∧␈↓problems␈αsolved␈α
using␈αSTRIPS␈α
and␈αPLANNER␈αand␈α
CONNIVER␈αare␈α
quasi-static,␈αand␈α
most␈αof
␈↓ α∧␈↓them are non-mental.

␈↓ α∧␈↓␈↓ αT␈↓↓Finite␈αstate␈αsearch␈α
problems␈↓␈αhave␈α␈↓↓Boolean␈αsearch␈α
problems␈↓␈αas␈αan␈αimportant␈α
subclass.␈α These
␈↓ α∧␈↓are formulated as follows:

␈↓ α∧␈↓␈↓ αTThe␈α∂state␈α∞of␈α∂the␈α∞system␈α∂is␈α∂characterized␈α∞by␈α∂the␈α∞values␈α∂of␈α∞Boolean␈α∂variables␈α∂␈↓↓p␈↓β1␈↓,...,␈↓↓p␈↓βn␈↓.␈α∞ An
␈↓ α∧␈↓allowed transformation of state is represented by a formula such as

␈↓ α∧␈↓␈↓ αT␈↓↓p␈↓β1␈↓↓∧␈↓λ-␈↓↓p␈↓β2␈↓↓∧␈↓λ-␈↓↓p␈↓β3␈↓↓∧p␈↓β4␈↓ => ␈↓↓p␈↓β3␈↓↓∧␈↓λ-␈↓↓p␈↓β4␈↓↓∧p␈↓β6␈↓.

␈↓ α∧␈↓␈↓ αTThe␈α∞meaning␈α∞of␈α
the␈α∞formula␈α∞is␈α∞that␈α
if␈α∞a␈α∞state␈α∞satisfies␈α
the␈α∞premiss␈α∞of␈α∞the␈α
transformation,
␈↓ α∧␈↓then␈αthe␈αtransformation␈αtakes␈αit␈αinto␈αa␈αstate␈αsatisfying␈αthe␈αconclusion,␈αwhere␈αunmentioned␈α␈↓↓p␈↓'s␈αare
␈↓ α∧␈↓left unchanged.

␈↓ α∧␈↓␈↓ αTThe desired state is characterized by a similar formula.

␈↓ α∧␈↓␈↓ αTThere␈αis␈αa␈αstraightforward␈αbreadth␈αfirst␈αsearch␈αalgorithm␈αfor␈αa␈αsequence␈αof␈αtransformations
␈↓ α∧␈↓leading␈α
to␈α
the␈α
desired␈α
final␈α
state.␈α It␈α
represents␈α
a␈α
state␈α
by␈α
a␈αBoolean␈α
vector,␈α
e.g.␈α
by␈α
the␈α
bits␈α
in␈αa
␈↓ α∧␈↓machine␈α∞word.␈α
 The␈α∞transformation␈α
is␈α∞represented␈α
by␈α∞four␈α
Boolean␈α∞words,␈α
a␈α∞mask␈α
each␈α∞for␈α
the
␈↓ α∧␈↓left␈α
and␈α
right␈α
parts␈α
and␈α
vectors␈α
whose␈α
ones␈α
correspond␈α
to␈α
the␈α
unnegated␈α
propositional␈αvariables␈α
in
␈↓ α∧␈↓the␈αleft␈α
and␈αright␈α
parts.␈α If␈α
the␈αstate␈α
is␈αdenoted␈α
by␈α␈↓↓s,␈↓␈α
the␈αmasks␈α
by␈α␈↓↓m␈↓βL␈↓␈α
and␈α␈↓↓m␈↓βR␈↓␈α
respectively,␈αand␈α
the
␈↓ α∧␈↓left␈α∀and␈α∃right␈α∀parts␈α∃by␈α∀␈↓↓L␈↓␈α∀and␈α∃␈↓↓R␈↓␈α∀respectively,␈α∃then␈α∀the␈α∀condition␈α∃for␈α∀applicability␈α∃of␈α∀the
␈↓ α∧␈↓transformation is

␈↓ α∧␈↓␈↓ αT␈↓↓m␈↓βL␈↓ ∧ ␈↓↓s␈↓ = ␈↓↓L␈↓

␈↓ α∧␈↓␈↓ ε|1␈↓ ∧
␈↓ α∧␈↓Finitary Search␈↓ εP␈↓πdraft␈↓␈↓ 
IMarch 4, 1976


␈↓ α∧␈↓␈↓ αTand the state resulting from the transformation is

␈↓ α∧␈↓␈↓ αT(␈↓↓m␈↓βR␈↓ ∧ ␈↓↓s)␈↓ ∨ ␈↓↓R,␈↓


␈↓ α∧␈↓␈↓ αTassuming the logical operators are given a bitwise interpretation.

␈↓ α∧␈↓␈↓ αTTherefore,␈αa␈αtransformation␈αcan␈αbe␈αapplied␈αto␈αa␈αstate␈αin␈αa␈αfew␈αmachine␈αinstructions,␈αand␈αit
␈↓ α∧␈↓seems␈αthat␈αproblems␈αinvolving␈αup␈α
to␈αsay␈αtwenty␈αBoolean␈αvariables␈α
can␈αbe␈αdone␈αin␈αa␈α
few␈αseconds
␈↓ α∧␈↓by␈α
a␈α
program␈α∞whose␈α
basic␈α
loop␈α∞computes␈α
the␈α
successors␈α∞of␈α
the␈α
newly␈α∞found␈α
states␈α
and␈α∞sorts␈α
the
␈↓ α∧␈↓newly␈α∂found␈α∂states␈α∞against␈α∂the␈α∂set␈α∂of␈α∞all␈α∂states␈α∂found␈α∞so␈α∂far␈α∂in␈α∂order␈α∞to␈α∂discard␈α∂old␈α∂states.␈α∞ (If
␈↓ α∧␈↓previously␈α∩found␈α∩states␈α∩are␈α∩not␈α∩discarded,␈α∩then␈α∩the␈α∩algorithm␈α∩will␈α∩blow␈α∩up␈α∩on␈α∩rather␈α∩small
␈↓ α∧␈↓problems).␈α The␈αalgorithm␈αwill␈αusually␈αrun␈αout␈αof␈αmain␈αmemory␈αbefore␈αit␈αruns␈αout␈αof␈αtime␈αso␈αthat
␈↓ α∧␈↓secondary storage may be appropriately used.

␈↓ α∧␈↓␈↓ αTIn␈α⊂the␈α⊂general␈α∂form␈α⊂of␈α⊂the␈α∂finite␈α⊂state␈α⊂search␈α∂problem,␈α⊂the␈α⊂state␈α∂is␈α⊂characterized␈α⊂by␈α∂the
␈↓ α∧␈↓values␈αof␈αa␈αnumber␈αof␈αvariables␈αeach␈αtaking␈αvalues␈αin␈αsmall␈αfinite␈αsets.␈α For␈αexample␈αthere␈αmight
␈↓ α∧␈↓be␈α
variables␈α
␈↓↓x␈↓β1␈↓,...,␈↓↓x␈↓β5␈↓,␈α
where␈α
␈↓↓x␈↓β1␈↓␈α
takes␈α
the␈α
values␈α
0,...,4,␈α
and␈α
␈↓↓x␈↓β2␈↓␈α
takes␈α
values␈α
0,...,7,␈α
etc.␈α
 The␈α
premiss␈α
of
␈↓ α∧␈↓a transformation is a conjunction such as

␈↓ α∧␈↓␈↓ αT␈↓↓x␈↓β1␈↓=3∧␈↓↓x␈↓β2␈↓≠1∧␈↓↓x␈↓β4␈↓=3,


␈↓ α∧␈↓␈↓ αTand the conclusion is a collection of assignments such as

␈↓ α∧␈↓␈↓ αT␈↓↓x␈↓β1␈↓←2;␈↓↓x␈↓β3␈↓←4;␈↓↓x␈↓β5␈↓←0.

␈↓ α∧␈↓␈↓ αTThe␈αtransformations␈α
are␈αinterpreted␈α
just␈αas␈αin␈α
the␈αBoolean␈α
case,␈αi.e.␈α if␈α
a␈αstate␈α
satisfies␈αthe
␈↓ α∧␈↓premiss␈α∞of␈α∞the␈α∞transformation,␈α∞it␈α∞can␈α∞be␈α∞transformed␈α∞by␈α∞making␈α∞the␈α∞assignment␈α∞specified␈α∂in␈α∞its
␈↓ α∧␈↓conclusion.

␈↓ α∧␈↓␈↓ αTThere␈αis␈αalso␈α
a␈αfast␈α␈↓↓standard␈↓␈α␈↓↓algorithm␈↓␈α
for␈αthe␈αgeneral␈αcase␈α
of␈αfinite␈αstate␈αsearch.␈α
 It␈αpacks
␈↓ α∧␈↓the␈α
values␈α
of␈α∞the␈α
state␈α
variables␈α∞into␈α
a␈α
machine␈α∞word␈α
leaving␈α
an␈α∞unused␈α
␈↓↓guard␈↓␈α
␈↓↓bit␈↓␈α∞between␈α
the
␈↓ α∧␈↓strings␈αof␈αbits␈αrepresenting␈αthe␈αcomponents.␈α The␈αpremiss␈αof␈αa␈αtransformation␈αis␈αtested␈αin␈αparallel
␈↓ α∧␈↓in␈α∪the␈α∪following␈α∪way:␈α∪First␈α∪we␈α∩␈↓↓and␈↓␈α∪the␈α∪state␈α∪with␈α∪a␈α∪mask␈α∩that␈α∪has␈α∪all␈α∪␈↓αone␈↓'s␈α∪in␈α∪the␈α∩fields
␈↓ α∧␈↓coresponding␈α∩to␈α∪the␈α∩variables␈α∪subjected␈α∩to␈α∪conditions.␈α∩ We␈α∪then␈α∩␈↓↓exclusive␈↓␈α∪␈↓↓or␈↓␈α∩with␈α∪the␈α∩word
␈↓ α∧␈↓representing␈α
the␈α
right␈α
hand␈α
sides␈α
of␈α
the␈α
conditions␈α
of␈α
the␈α
premiss,␈α
so␈α
that␈α
the␈α
new␈α
word␈αhas␈α
zeroes
␈↓ α∧␈↓in␈α⊂precisely␈α⊂those␈α⊂fields␈α⊂where␈α∂the␈α⊂components␈α⊂of␈α⊂the␈α⊂state␈α∂equal␈α⊂the␈α⊂right␈α⊂hand␈α⊂sides␈α⊂of␈α∂the
␈↓ α∧␈↓conditions.␈α Next␈αwe␈α␈↓↓add␈↓␈αa␈αword␈αwith␈αall␈α
␈↓αone␈↓'s␈αin␈αthose␈αfields␈αgetting␈αa␈αcarry␈αinto␈αthe␈α
guard␈αbits
␈↓ α∧␈↓where␈α⊂the␈α⊂equalities␈α⊂are␈α⊂not␈α⊂satisfied.␈α⊂ Now␈α⊂we␈α⊃mask␈α⊂out␈α⊂all␈α⊂but␈α⊂the␈α⊂guard␈α⊂bits␈α⊂and␈α⊃test␈α⊂for
␈↓ α∧␈↓equality␈αwith␈αa␈αword␈αthat␈αhas␈α␈↓αone␈↓'s␈αin␈αprecisely␈αthose␈αguard␈αbits␈αwhere␈αinequality␈αwas␈αwanted.␈α If
␈↓ α∧␈↓the␈αcondition␈αis␈αsatisfied,␈αmaking␈αthe␈αtransformation␈αis␈αjust␈αa␈αmatter␈αof␈αmasking␈αout␈αthe␈αfields␈αto
␈↓ α∧␈↓which assignments are made and ␈↓↓or␈↓ing in the right hand sides of the assignments.






␈↓ α∧␈↓␈↓ ε|2␈↓ ∧
␈↓ α∧␈↓Finitary Search␈↓ εP␈↓πdraft␈↓␈↓ 
IMarch 4, 1976


␈↓ α∧␈↓α␈↓ αT2. Examples

␈↓ α∧␈↓␈↓ αT1.␈α⊂Suppose␈α⊂there␈α⊂are␈α⊂four␈α⊂blocks␈α⊂called␈α⊂␈↓↓A,␈↓␈α⊂␈↓↓B,␈↓␈α⊂␈↓↓C,␈↓␈α⊂and␈α⊂␈↓↓D␈↓␈α⊂on␈α⊂a␈α⊂table,␈α⊂and␈α⊂that␈α⊂a␈α⊂state␈α⊂is
␈↓ α∧␈↓characterized␈α∞by␈α
the␈α∞set␈α∞of␈α
relations␈α∞of␈α∞the␈α
form␈α∞␈↓↓on(x,y)␈↓␈α
that␈α∞are␈α∞satisfied.␈α
 Since␈α∞there␈α∞are␈α
four
␈↓ α∧␈↓blocks␈α
each␈αof␈α
which␈αcan␈α
be␈α
on␈αany␈α
of␈αthe␈α
other␈α
blocks␈αor␈α
the␈αtable,␈α
the␈α
state␈αis␈α
determined␈αby␈α
the
␈↓ α∧␈↓values␈α⊂of␈α∂16␈α⊂Boolean␈α∂variables.␈α⊂ If␈α∂we␈α⊂have␈α∂␈↓↓p␈↓β1␈↓↓␈α⊂=␈α∂on(A,B),␈α⊂p␈↓β2␈↓↓␈α∂=␈α⊂on(A,C),␈α∂p␈↓β3␈↓↓␈α⊂=␈α∂on(A,D),␈α⊂p␈↓β4␈↓↓␈α∂=
␈↓ α∧␈↓↓on(A,Table), p␈↓β5␈↓↓ = on(B,A)␈↓, etc. in the obvious way, then the allowed transformations are

␈↓ α∧␈↓␈↓ αT ␈↓λ-␈↓␈↓↓p␈↓β5␈↓∧␈↓λ-␈↓␈↓↓p␈↓β9␈↓∧␈↓λ-␈↓␈↓↓p␈↓β13␈↓∧␈↓λ-␈↓␈↓↓p␈↓β10␈↓∧␈↓λ-␈↓␈↓↓p␈↓β14␈↓ => ␈↓↓p␈↓β1␈↓∧␈↓λ-␈↓␈↓↓p␈↓β2␈↓∧␈↓λ-␈↓␈↓↓p␈↓β3␈↓∧␈↓λ-␈↓␈↓↓p␈↓β4␈↓, etc. -

␈↓ α∧␈↓␈↓ αTone␈αtransformation␈αgiving␈αthe␈αconditions␈αfor␈αputting␈αeach␈αblock␈αon␈αeach␈αother␈αor␈αthe␈αtable.
␈↓ α∧␈↓While␈αthere␈αare␈α
2␈↓∧16␈↓␈α=␈α65536␈α
states,␈αonly␈α4␈↓∧4␈↓␈α=␈α
256␈αof␈αthem␈α
are␈αlegitimate␈αsince␈α
a␈αblock␈αis␈αin␈α
exactly
␈↓ α∧␈↓one place in any given state.  Therefore, the search for a path to a goal will be quite fast.

␈↓ α∧␈↓␈↓ αTThe␈α
same␈α
problem␈α
can␈α
be␈α
represented␈α
as␈α
a␈α
finite␈α
state␈α
search␈α
problem␈α
by␈α∞introducing␈α
the
␈↓ α∧␈↓variables␈α␈↓↓x␈↓β1␈↓,...,␈↓↓x␈↓β4␈↓␈αeach␈αtaking␈αthe␈α
values␈α0␈αthrough␈α4␈αand␈α
giving␈αthe␈αblock␈αor␈αtable␈α
that␈αsupports
␈↓ α∧␈↓each␈α
block␈α
and␈α
therefore␈α
5␈↓∧4␈↓␈α
=␈α
625␈α
states.␈α
 If␈α
we␈α
use␈α
a␈α
different␈α
space␈α
for␈α
the␈α
support␈α
of␈α
each␈α
block,
␈↓ α∧␈↓then␈α
we␈α
are␈α
down␈α
to␈α
the␈α
minimum␈α
256␈αstates.␈α
 Naturally,␈α
if␈α
a␈α
human␈α
is␈α
setting␈α
up␈α
the␈αproblem,
␈↓ α∧␈↓this␈αis␈α
the␈αright␈αthing␈α
to␈αdo,␈α
but␈αif␈αa␈α
program␈αis␈α
generating␈αthe␈αfinite␈α
state␈αsearch␈α
problem␈αfrom
␈↓ α∧␈↓the␈αproblem␈α
expressed␈αin␈α
a␈αdifferent␈α
formalism,␈αwe␈α
may␈αstill␈α
get␈αa␈α
good␈αresult␈α
even␈αif␈α
it␈αmisses␈α
the
␈↓ α∧␈↓fact that a block cannot be on top of itself.

␈↓ α∧␈↓␈↓ αTAgain␈α
there␈α
are␈α
sixteen␈α
transformations,␈α
and␈α
the␈α
one␈α
corresponding␈α
to␈α
the␈α
above␈α
Boolean
␈↓ α∧␈↓transformation is

␈↓ α∧␈↓␈↓ αT␈↓↓x␈↓β2␈↓≠1 ∧ ␈↓↓x␈↓β3␈↓l≠1 ∧ ␈↓↓x␈↓β4␈↓≠1 ∧ ␈↓↓x␈↓β3␈↓≠2 ∧ ␈↓↓x␈↓β4␈↓≠2 => ␈↓↓x␈↓β1␈↓ ← 2.

␈↓ α∧␈↓␈↓ αTUnfortunately,␈α∩the␈α∩standard␈α∩algorithm␈α⊃for␈α∩finite␈α∩state␈α∩search␈α⊃won't␈α∩work␈α∩for␈α∩the␈α⊃block
␈↓ α∧␈↓moving␈α
problem,␈α
because␈α
the␈α
variable␈α
␈↓↓x␈↓β3␈↓,␈α∞for␈α
example,␈α
must␈α
satisfy␈α
two␈α
inequality␈α∞conditions␈α
in
␈↓ α∧␈↓the␈α
first␈α
transformation.␈α
 This␈α
can␈α
be␈α
fixed␈α
by␈α
representing␈α
each␈α
variable␈α
twice,␈α∞and␈α
everything
␈↓ α∧␈↓will still fit in a machine word.

␈↓ α∧␈↓␈↓ αT2.␈α
The␈αsecond␈α
example␈αis␈α
the␈α␈↓↓Tower␈α
of␈α
Hanoi␈↓␈αproblem.␈α
 There␈αis␈α
a␈αvariable␈α
for␈α
each␈αdisk
␈↓ α∧␈↓taking␈αvalue␈α1,␈α2,␈αor␈α3␈αstating␈αwhat␈αspike␈αit␈αis␈αon.␈α A␈αtwelve␈αdisk␈αstate␈αis␈αrepresentable␈αin␈αa␈α36␈αbit
␈↓ α∧␈↓word,␈α∞and␈α
there␈α∞are␈α
3␈↓∧12␈↓␈α∞=␈α
531441␈α∞states␈α
to␈α∞be␈α
searched␈α∞so␈α
the␈α∞problem␈α
is␈α∞quite␈α
feasible␈α∞by␈α
this
␈↓ α∧␈↓brute force method.


␈↓ α∧␈↓α␈↓ αT3. Improved Algorithms

␈↓ α∧␈↓␈↓ αTThe␈α∞standard␈α∞algorithms␈α∞for␈α∞Boolean␈α∞or␈α∞finite␈α∞state␈α∞search␈α∞may␈α∞be␈α∞the␈α∞best␈α∂algorithm␈α∞in
␈↓ α∧␈↓general␈αalthough␈αI␈αdoubt␈αit.␈α However,␈αit␈αwould␈αseem␈αthat␈αmost␈αproblems␈αarising␈αin␈αAI␈αwill␈αhave
␈↓ α∧␈↓structures that permit heuristics that greatly reduce the search.

␈↓ α∧␈↓␈↓ αTThe␈α
finite␈αstate␈α
search␈α
algorithm␈αcan␈α
be␈αimproved␈α
by␈α
generalizing␈αthe␈α
conditions␈α
that␈αcan
␈↓ α∧␈↓serve␈αas␈α
premissses.␈α There␈α
is␈αno␈α
point␈αin␈α
introducing␈αdisjunctions␈α
as␈αwell␈α
as␈αconjunctions␈αinto␈α
the
␈↓ α∧␈↓premiss␈αbecause␈αthis␈αis␈αhandled␈αby␈αhaving␈αa␈αcollection␈αof␈αrules␈α-␈αone␈αfor␈αeach␈αdisjunct.␈α
 However,


␈↓ α∧␈↓␈↓ ε|3␈↓ ∧
␈↓ α∧␈↓Finitary Search␈↓ εP␈↓πdraft␈↓␈↓ 
IMarch 4, 1976


␈↓ α∧␈↓we␈αcan␈α
allow␈αranges␈α
of␈αvalues␈α
for␈αthe␈αvariables.␈α
 It␈αis␈α
necessary␈αonly␈α
to␈αchoose␈α
suitable␈αconstants
␈↓ α∧␈↓represent␈α
the␈αvalue␈α
of␈αeach␈α
variable␈αtwice␈α
by␈αthe␈α
contents␈αof␈α
field␈αin␈α
the␈αword␈α
and␈αchoose␈α
suitable
␈↓ α∧␈↓constants␈αto␈α
be␈αadded␈α
to␈αthe␈α
fields.␈α Then␈α
the␈αvalues␈α
of␈αthe␈α
guard␈αbits␈α
tell␈αwhether␈α
the␈αaddition
␈↓ α∧␈↓produced␈α∂overflow␈α∂and␈α∂after␈α⊂masking␈α∂out␈α∂all␈α∂but␈α∂certain␈α⊂guard␈α∂bits,␈α∂the␈α∂program␈α∂can␈α⊂test␈α∂for
␈↓ α∧␈↓equality with a suitable constant.  I don't yet have examples where this pays off.

␈↓ α∧␈↓␈↓ αTA␈α∪second␈α∪possible␈α∩improvement␈α∪involves␈α∪arranging␈α∪the␈α∩transformations␈α∪into␈α∪a␈α∪tree␈α∩of
␈↓ α∧␈↓conditions, so that certain transformations are tested only if suitable conditions are satisfied.

␈↓ α∧␈↓␈↓ αTThe␈αabove␈αimprovements␈αdon't␈αchange␈αthe␈αsearch␈αspace;␈αthey␈αmerely␈αreduce␈αthe␈αnumber␈αof
␈↓ α∧␈↓transformations.␈α∞ However,␈α
the␈α∞␈↓↓Tower␈α
of␈α∞Hanoi␈↓␈α
problem␈α∞is␈α
reduced␈α∞by␈α
a␈α∞heuristic␈α
that␈α∞seems␈α
to
␈↓ α∧␈↓have␈αwide␈αapplicability.␈α Namely␈αthe␈αbottom␈αdisk␈αhas␈αto␈αbe␈αmoved,␈αand␈αthe␈αcondition␈αfor␈αmoving
␈↓ α∧␈↓it␈α
is␈α
that␈α
none␈αof␈α
the␈α
other␈α
disks␈α
be␈αon␈α
it␈α
or␈α
on␈α
its␈αdestination␈α
spike.␈α
 Therefore,␈α
the␈αproblem␈α
splits
␈↓ α∧␈↓into␈αthree␈αparts␈α-␈αmoving␈αthe␈αother␈αdisks,␈αmoving␈αthe␈αbottom␈αdisk,␈αand␈αmoving␈αthe␈αothers␈αagain.
␈↓ α∧␈↓Suppose␈αthat␈αa␈αheuristic␈αis␈αused␈αthat␈αcan␈αrecognize␈αthis.␈α Then␈αit␈αwill␈αalso␈αrecognize␈αthat␈αeach␈αof
␈↓ α∧␈↓the␈αmoves␈αof␈α␈↓↓n-1␈↓␈αdisks␈αhas␈αthe␈αsame␈αcharacter.␈α Thus␈αthere␈αwon't␈αbe␈αany␈αblind␈αsearch␈αof␈αa␈αspace
␈↓ α∧␈↓of␈α3␈↓∧n␈↓␈αpoints,␈αbut␈αrather␈αa␈αdirect␈αproblem␈αreduction␈αthat␈αwill␈αeventually␈αinvolve␈α2␈↓∧n␈↓-1␈αtrivial␈α
moves.
␈↓ α∧␈↓This␈αheuristic␈αdoes␈αnot␈αexplicitly␈αrecognize␈αthe␈αsymmetries␈αof␈αthe␈αproblem␈αthat␈αpermit␈αus␈αto␈αsee␈α
in
␈↓ α∧␈↓a small amount of reasoning that the ␈↓↓Tower of Hanoi␈↓ is solvable for any ␈↓↓n.␈↓

␈↓ α∧␈↓␈↓ αTThere␈α∩is␈α∩another␈α∩heuristic␈α∩that␈α∩also␈α∪solves␈α∩the␈α∩␈↓↓Tower␈α∩of␈α∩Hanoi␈↓␈α∩problem.␈α∪ Namely␈α∩the
␈↓ α∧␈↓conditions␈α∞for␈α∂moving␈α∞the␈α∂top␈α∞disk␈α∂are␈α∞null␈α∂and␈α∞it␈α∂can␈α∞be␈α∂moved␈α∞to␈α∂any␈α∞spike.␈α∂ Therefore,␈α∞its
␈↓ α∧␈↓variable␈α⊂can␈α∂be␈α⊂given␈α⊂an␈α∂arbitrary␈α⊂value␈α⊂without␈α∂changing␈α⊂the␈α⊂values␈α∂of␈α⊂the␈α⊂other␈α∂variables.
␈↓ α∧␈↓This␈α∞means␈α∞that␈α
when␈α∞the␈α∞position␈α
of␈α∞the␈α∞top␈α
disk␈α∞occurs␈α∞in␈α
a␈α∞condition␈α∞form␈α∞moving␈α
another
␈↓ α∧␈↓disk,␈αthis␈αpart␈αof␈αthe␈αcondition␈αcan␈αalways␈αbe␈αsatisfied,␈αand␈αtherefore␈αwe␈αcan␈αget␈αa␈α␈↓↓reduced␈α
set␈αof
␈↓ α∧␈↓↓transformations␈↓␈αby␈αeliminating␈αthe␈α
conditions␈αon␈αthe␈αtop␈α
disk␈αfrom␈αthe␈αconjunctions.␈α However,␈α
in
␈↓ α∧␈↓this␈α∞reduced␈α∞set,␈α∞the␈α∞second␈α∞disk␈α∞will␈α∞enjoy␈α∂the␈α∞property␈α∞of␈α∞the␈α∞top␈α∞disk␈α∞in␈α∞the␈α∞previous␈α∂set␈α∞of
␈↓ α∧␈↓transformations.  Successive application of this heuristic will wipe out the entire problem.

␈↓ α∧␈↓␈↓ αTLet's␈αcall␈α
these␈αheuristics␈αthe␈α
␈↓↓bottom-up␈↓␈αand␈α␈↓↓top-down␈↓␈α
heuristics␈αrespectively.␈α In␈α
the␈α␈↓↓Tower
␈↓ α∧␈↓↓of␈α⊃Hanoi␈↓␈α⊃case,␈α⊃either␈α⊃trivializes␈α⊃the␈α⊃problem,␈α⊂and␈α⊃one␈α⊃might␈α⊃suspect␈α⊃they␈α⊃are␈α⊃equivalent.␈α⊂ In
␈↓ α∧␈↓general,␈α∞it␈α
would␈α∞seem␈α∞that␈α
they␈α∞are␈α
not␈α∞equivalent␈α∞but␈α
rather␈α∞dual␈α
and␈α∞correspond␈α∞to␈α
problem
␈↓ α∧␈↓reductions␈αmuch␈αused␈αin␈αhuman␈αproblem␈αsolving.␈α Suppose␈αwe␈αwant␈αto␈αtravel␈αfrom␈αSan␈αFrancisco
␈↓ α∧␈↓to␈α
Peking.␈α
 Top-down␈α
tells␈αus␈α
that␈α
when␈α
we␈αhave␈α
to␈α
change␈α
planes␈αin␈α
an␈α
intermediate␈α
city,␈αwe␈α
will
␈↓ α∧␈↓always␈α∂be␈α⊂able␈α∂to␈α∂find␈α⊂the␈α∂gate␈α⊂of␈α∂the␈α∂outgoing␈α⊂plane,␈α∂so␈α∂we␈α⊂can␈α∂eliminate␈α⊂the␈α∂corresponding
␈↓ α∧␈↓variables␈αfrom␈αthe␈αproblem.␈α Bottom-up␈αmay␈αtell␈αus␈αthat␈αthe␈αmain␈αproblem␈αis␈αgetting␈αthe␈αChinese
␈↓ α∧␈↓visa,␈αand␈α
the␈αproblem␈α
can␈αbe␈α
divided␈αinto␈α
getting␈αthe␈α
visa␈αand␈α
then␈αusing␈α
it.␈α In␈α
fact,␈αthe␈α
problem
␈↓ α∧␈↓of getting to Peking has a more complex structure.




␈↓ α∧␈↓α␈↓ αT4. Reduction of Problems to Finite State

␈↓ α∧␈↓␈↓ αTThe␈α
blocks␈α
problem␈α
can␈α
be␈α
axiomatized␈α
in␈α
first␈α
order␈α
logic␈α
as␈α
follows:␈α
We␈α
use␈α
the␈αvariable␈α
␈↓↓s␈↓
␈↓ α∧␈↓to␈αrepresent␈αstates␈αof␈α
the␈αworld,␈αand␈α␈↓↓move(x,y,s)␈↓␈α
to␈αrepresent␈αthe␈αnew␈α
state␈αof␈αthe␈αworld␈αthat␈α
results
␈↓ α∧␈↓from␈αmoving␈αthe␈αblock␈α␈↓↓x␈↓␈αonto␈αthe␈αblock␈α␈↓↓y␈↓␈αwhen␈αthe␈αworld␈αis␈αin␈αstate␈α␈↓↓s.␈↓␈α(In␈αthe␈α"situation␈α
calculus"


␈↓ α∧␈↓␈↓ ε|4␈↓ ∧
␈↓ α∧␈↓Finitary Search␈↓ εP␈↓πdraft␈↓␈↓ 
IMarch 4, 1976


␈↓ α∧␈↓of␈α
(McCarthy␈α
and␈α
Hayes␈α
1970),␈α
␈↓↓s␈↓␈α
is␈α∞a␈α
situation␈α
variable).␈α
 Statements␈α
about␈α
one␈α
block␈α∞being␈α
on
␈↓ α∧␈↓top␈α∞of␈α∂another␈α∞can␈α∞be␈α∂represented␈α∞in␈α∂two␈α∞ways:␈α∞one␈α∂leads␈α∞to␈α∞Boolean␈α∂search␈α∞problems␈α∂and␈α∞the
␈↓ α∧␈↓other␈αleads␈α
to␈αfinite␈α
state␈αsearch␈α
problems.␈α The␈α
first␈αis␈α
to␈αintroduce␈α
a␈αrelation␈α
␈↓↓on(x,y,s)␈↓␈αasserting
␈↓ α∧␈↓that␈αthe␈α
block␈α␈↓↓x␈↓␈α
is␈αon␈α
the␈αblock␈α
␈↓↓y␈↓␈αin␈αstate␈α
␈↓↓s,␈↓␈αand␈α
the␈αsecond␈α
is␈αto␈α
introduce␈αa␈αfunction␈α
␈↓↓support(x,s).␈↓
␈↓ α∧␈↓These are related by

␈↓ α∧␈↓␈↓ αT∀␈↓↓x y s.(y = support(x,s) ≡ on(x,y,s)).␈↓

␈↓ α∧␈↓␈↓ αTThe axioms for moving are

␈↓ α∧␈↓␈↓ αT∀␈↓↓x y s.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

␈↓ α∧␈↓↓␈↓ αT⊃ on(x,y,move(x,y,s)) ∧ ∀z.(z≠y ⊃ ␈↓λ-␈↓↓on(x,z,move(x,y,s))␈↓

␈↓ α∧␈↓␈↓ αT∧ ∀w z.(w≠x ⊃ on(w,z,move(x,y,s)) ≡ on(w,z,s)))

␈↓ α∧␈↓␈↓ αTusing ␈↓↓on,␈↓ and

␈↓ α∧␈↓␈↓ αT∀␈↓↓x y s.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

␈↓ α∧␈↓↓␈↓ αT⊃ support(x,move(x,y,s)) = y ∧ ∀w.(w≠x ⊃ support(w,move(x,y,s)) = support(w,s))).␈↓

␈↓ α∧␈↓␈↓ αTIf␈αwe␈αadmit␈αconditional␈αexpressions␈αin␈αour␈αformalism␈αfor␈αfirst␈αorder␈αlogic,␈αthe␈αsecond␈α
axiom
␈↓ α∧␈↓simplifies slightly to

␈↓ α∧␈↓␈↓ αT∀␈↓↓x y s w.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

␈↓ α∧␈↓↓␈↓ αT⊃ support(w,move(x,y,s)) = ␈↓αif␈↓↓ w=x ␈↓αthen␈↓↓ y ␈↓αelse␈↓↓ support(w,s)).␈↓

␈↓ α∧␈↓␈↓ αTThe expression ␈↓↓clear(x,s)␈↓ which appears above is defined by

␈↓ α∧␈↓␈↓ αT␈↓↓∀x s.(clear(x,s) ≡ ∀z.␈↓λ-␈↓↓on(z,x.s))␈↓

␈↓ α∧␈↓␈↓ αTor

␈↓ α∧␈↓␈↓ αT∀␈↓↓x s.(clear(x,s) ≡ ∀z.(support(z,s) ≠ x))␈↓.

␈↓ α∧␈↓␈↓ αTThese␈α
axioms␈α
are␈α
correct␈αfor␈α
the␈α
␈↓↓quasi-static␈↓␈α
block␈αmoving␈α
problem␈α
regardless␈α
of␈αhow␈α
many
␈↓ α∧␈↓blocks␈α
there␈α
are.␈α To␈α
obtain␈α
a␈α
Boolean␈αsearch␈α
or␈α
finite-state␈α
search␈αproblem,␈α
a␈α
person␈αor␈α
computer
␈↓ α∧␈↓program␈αmust␈αmake␈αappropriate␈αsubstitutions␈αof␈αa␈αsmall␈αfinite␈αnumber␈αof␈αblocks␈αinto␈αthe␈αaxioms,
␈↓ α∧␈↓settle␈αon␈αan␈αinitial␈αstate␈αand␈αfinal␈αcondition␈αand␈αgive␈αa␈αspecial␈αrole␈αto␈αthe␈αfunction␈α␈↓↓move(x,y,s)␈↓␈α
and
␈↓ α∧␈↓to the variable ␈↓↓s␈↓ itself.

␈↓ α∧␈↓␈↓ αTSuch␈αa␈αprocess␈αis␈αanalogous␈αto␈αtrying␈αto␈αprove␈αfirst␈αorder␈αlogic␈αproblems␈αby␈αmaking␈αa␈αfinite
␈↓ α∧␈↓set␈α
of␈α
substitutions␈α
from␈α
the␈α
Herbrand␈α
universe␈α
into␈α
the␈α
axioms␈α
and␈α
then␈α
solving␈α
a␈α
problem␈α
in
␈↓ α∧␈↓propositional␈α∂calculus.␈α⊂ The␈α∂trick␈α⊂in␈α∂either␈α∂case␈α⊂is␈α∂to␈α⊂find␈α∂the␈α∂right␈α⊂set␈α∂of␈α⊂substitutions.␈α∂ Such
␈↓ α∧␈↓methods␈αfor␈αpredicate␈αcalculus␈αwere␈αproposed␈αby␈αMartin␈αDavis,␈αand␈αhe␈αexperimented␈αwith␈α
a␈αvey


␈↓ α∧␈↓␈↓ ε|5␈↓ ∧
␈↓ α∧␈↓Finitary Search␈↓ εP␈↓πdraft␈↓␈↓ 
IMarch 4, 1976


␈↓ α∧␈↓simple␈α∀form,␈α∪but␈α∀they␈α∀were␈α∪superseded␈α∀by␈α∀the␈α∪resolution␈α∀methods␈α∀that␈α∪don't␈α∀make␈α∀all␈α∪the
␈↓ α∧␈↓substitutions at once.

␈↓ α∧␈↓␈↓ αTIn␈αmy␈αopinion,␈α
the␈αvery␈αfast␈αalgorithms␈α
that␈αcan␈αbe␈αused␈α
after␈αthe␈αsubstitutions␈α
have␈αbeen
␈↓ α∧␈↓made␈α(e.g.␈αthe␈αTAUT␈αalgorithm␈αfrom␈αFOL␈αby␈αChandra␈αand␈αWeyhrauch)␈αmake␈αit␈αworthwhile␈αto
␈↓ α∧␈↓try to find heuristics for making a good set of substitutions.


␈↓ α∧␈↓α␈↓ αT5. Hardware

␈↓ α∧␈↓␈↓ αTThe␈αstandard␈αalgorithms␈α
for␈αBoolean␈αand␈α
finite␈αstate␈αsearch␈α
can␈αbe␈αimplemented␈αin␈α
parallel
␈↓ α∧␈↓hardware␈αand␈αshould␈αrun␈αextremely␈αfast.␈α The␈αidea␈αis␈αto␈αhave␈αparallel␈αsimple␈αprocessors␈αgenerate
␈↓ α∧␈↓points␈αin␈αthe␈αsearch␈αspace␈αand␈αcompute␈αneighbors␈αin␈αparallel␈αand␈αgenerate␈αpointers␈αto␈αneighbors.
␈↓ α∧␈↓Then␈αthe␈αdistance␈αfrom␈αthe␈αinitial␈αpoint␈α
can␈αpropagate␈αthrough␈αthe␈αspace,␈αand␈αthe␈α
solution␈αpath
␈↓ α∧␈↓will␈αbe␈αfound␈αin␈αa␈αnumber␈αof␈αstpes␈αproportional␈αto␈αthe␈αlength␈αof␈αthe␈αshortest␈αpath.␈α We␈αenvisage
␈↓ α∧␈↓such␈α
parallel␈α∞hardware␈α
as␈α
a␈α∞satellite␈α
to␈α∞a␈α
conventional␈α
computer␈α∞that␈α
would␈α
give␈α∞it␈α
parts␈α∞of␈α
the
␈↓ α∧␈↓search␈α⊂space␈α⊂to␈α⊃explore.␈α⊂ In␈α⊂the␈α⊃design,␈α⊂the␈α⊂top-down␈α⊂and␈α⊃bottom-up␈α⊂heuristics␈α⊂must␈α⊃also␈α⊂be
␈↓ α∧␈↓considered.

␈↓ α∧␈↓␈↓ αTNaturally,␈α∩much␈α⊃more␈α∩must␈α⊃be␈α∩learned␈α∩about␈α⊃the␈α∩algorithms␈α⊃for␈α∩reducing␈α∩problems␈α⊃to
␈↓ α∧␈↓Boolean and finite-state searches, before one could seriously contemplate building such hardware.




␈↓ α∧␈↓α␈↓ αT6. Limitations

␈↓ α∧␈↓␈↓ αTSo␈αfar␈αas␈αI␈α
know,␈αthere␈αaren't␈αany␈α
significant␈αAI␈αproblems␈αthat␈α
directly␈αtake␈αa␈αfinitary␈α
form.
␈↓ α∧␈↓This␈α∞is␈α∞because␈α∞almost␈α∞all␈α∞intelligent␈α∞behavior␈α∞involves␈α∞the␈α∞application␈α∞of␈α∞general␈α∞laws,␈α∞even␈α
if
␈↓ α∧␈↓only␈αthe␈αlaws␈αgoverning␈αthe␈αeffects␈αof␈αmoving␈αblocks,␈αto␈αparticular␈αcases,␈αand␈αthe␈αfinitary␈αsystems
␈↓ α∧␈↓considered␈αin␈αthis␈α
paper␈αcome␈αup␈α
only␈αafter␈αthe␈αgeneral␈α
laws␈αhave␈αbeen␈α
instantiated.␈α Therefore,
␈↓ α∧␈↓the␈α
utility␈α
of␈α
the␈α
method␈αdepends␈α
on␈α
finding␈α
ways␈α
to␈αinstantiate␈α
the␈α
general␈α
laws␈α
before␈αthe␈α
search
␈↓ α∧␈↓is made.

␈↓ α∧␈↓␈↓ αTAnother␈α⊂way␈α⊂of␈α⊃seeing␈α⊂the␈α⊂limitations␈α⊂of␈α⊃finitary␈α⊂search␈α⊂is␈α⊂to␈α⊃try␈α⊂to␈α⊂apply␈α⊂it␈α⊃to␈α⊂games.
␈↓ α∧␈↓Suppose␈α
there␈α
are␈α
only␈α
five␈α∞pieces␈α
left␈α
on␈α
a␈α
chess␈α
board.␈α∞ Then␈α
we␈α
can␈α
use␈α
the␈α
locations␈α∞of␈α
the
␈↓ α∧␈↓pieces␈αas␈αvariables,␈αso␈α
the␈αposition␈αis␈αcharacterized␈α
by␈αthe␈αvalues␈αof␈α
five␈αsix-bit␈αquantities.␈α So␈α
far
␈↓ α∧␈↓so good since that will fit into one 36-bit machine word.

␈↓ α∧␈↓␈↓ αTAnother␈αmatter␈αthat␈αworks␈αout␈α
well␈αis␈αthe␈αsearch␈αalgorithm␈α
itself.␈α Instead␈αof␈αthe␈αsimple␈α
tree
␈↓ α∧␈↓search␈α
of␈α
the␈αprevious␈α
problems,␈α
we␈αwill␈α
need␈α
an␈α
α-β␈αsearch,␈α
but␈α
this␈αis␈α
helpful,␈α
because␈αit␈α
reduces
␈↓ α∧␈↓the␈α
size␈α
of␈α
the␈α
space␈α
to␈α
be␈α
searched.␈α
 The␈α
general␈α
search␈α
algorithm␈α
but␈α
the␈α
successors␈αcalculation␈α
is
␈↓ α∧␈↓just the application of a set of transformations.

␈↓ α∧␈↓␈↓ αTThe␈α∂first␈α⊂difficulty␈α∂is␈α⊂the␈α∂goal␈α⊂condition.␈α∂ In␈α⊂case␈α∂the␈α⊂goal␈α∂is␈α⊂checkmate,␈α∂the␈α⊂number␈α∂of
␈↓ α∧␈↓possible␈αgoal␈αstates␈αis␈αvery␈αlarge,␈αand␈αthey␈αare␈αnot␈αsummarized␈αby␈αgiving␈αvalues␈αto␈αa␈αsubset␈αof␈α
the
␈↓ α∧␈↓variables.␈α∩ However,␈α∩if␈α∩the␈α∩goal␈α∩were␈α∩merely␈α⊃to␈α∩promote␈α∩a␈α∩pawn,␈α∩the␈α∩goal␈α∩might␈α∩be␈α⊃simply
␈↓ α∧␈↓characterized.

␈↓ α∧␈↓␈↓ ε|6␈↓ ∧
␈↓ α∧␈↓Finitary Search␈↓ εP␈↓πdraft␈↓␈↓ 
IMarch 4, 1976


␈↓ α∧␈↓␈↓ αTThe␈α∞real␈α∞difficulty␈α∞is␈α∂that␈α∞there␈α∞would␈α∞be␈α∞too␈α∂many␈α∞transformations.␈α∞ There␈α∞would␈α∂be␈α∞at
␈↓ α∧␈↓least␈α
one␈αfor␈α
every␈αpair␈α
consisting␈αof␈α
an␈αinitial␈α
square␈αand␈α
destination␈αsquare␈α
for␈αeach␈α
piece,␈αi.e.
␈↓ α∧␈↓about␈α⊂5␈α⊂x␈α⊂64␈α⊃x␈α⊂10␈α⊂=␈α⊂3200.␈α⊃ Actually␈α⊂there␈α⊂would␈α⊂be␈α⊃several␈α⊂times␈α⊂that␈α⊂number,␈α⊃because␈α⊂the
␈↓ α∧␈↓condition␈αfor␈αmoving␈αa␈αpiece␈αfrom␈αa␈α
given␈αsquare␈αto␈αa␈αgiven␈αother␈αsquare␈αmight␈α
require␈αseveral
␈↓ α∧␈↓transformations.

␈↓ α∧␈↓␈↓ αTI␈α
can't␈α
quite␈α
convince␈α
myself␈α
that␈α
the␈α
formalism␈α
couldn't␈α
be␈α
made␈α
to␈α
work␈α
for␈α
small␈α
chess
␈↓ α∧␈↓endgames,␈αbut␈α
it␈αcertainly␈α
wouldn't␈αbe␈α
very␈αnatural.␈α
 In␈αfact,␈α
I␈αbelieve␈α
it␈αwould␈α
work␈αquite␈αwell␈α
for
␈↓ α∧␈↓some␈α␈↓↓go␈↓␈α
and␈αchecker␈α
end␈αgames.␈α
 In␈α␈↓↓go␈↓␈αproblems␈α
where␈αall␈α
the␈αmoves␈α
take␈αplace␈α
in␈αa␈αsmall␈α
region,
␈↓ α∧␈↓the␈αtransformation␈αrules␈αmay␈αbe␈αreasonably␈αfew,␈αbut␈αthe␈αgoal␈αcondition␈αmay␈αbe␈αrather␈αdifficult␈αto
␈↓ α∧␈↓compute.

␈↓ α∧␈↓␈↓ αTTo␈α
the␈α
extent␈αthat␈α
reduction␈α
to␈α
finitary␈αsearch␈α
is␈α
useful,␈α
it␈αwould␈α
satisfy␈α
some␈αpeople's␈α
desire
␈↓ α∧␈↓for␈αa␈αmethod␈αin␈αartificial␈αintelligence␈αthat␈αdoesn't␈αcome␈αfrom␈αnatural␈αintelligence,␈αsince␈αit␈αdepends
␈↓ α∧␈↓explicitly␈αon␈αa␈αcomputer's␈αability␈αto␈αmanipulate␈α
bits␈αof␈αinformation␈αvery␈αrapidly␈αonce␈αthe␈α
meaning
␈↓ α∧␈↓has been abstracted from them.

































␈↓ α∧␈↓␈↓ ε|7␈↓ ∧